In routing games, the network performance at equilibrium can be significantlyimproved if we remove some edges from the network. This counterintuitive fact,widely known as Braess's paradox, gives rise to the (selfish) network designproblem, where we seek to recognize routing games suffering from the paradox,and to improve the equilibrium performance by edge removal. In this work, weinvestigate the computational complexity and the approximability of the networkdesign problem for non-atomic bottleneck routing games, where the individualcost of each player is the bottleneck cost of her path, and the social cost isthe bottleneck cost of the network. We first show that bottleneck routing gamesdo not suffer from Braess's paradox either if the network is series-parallel,or if we consider only subpath-optimal Nash flows. On the negative side, weprove that even for games with strictly increasing linear latencies, it isNP-hard not only to recognize instances suffering from the paradox, but also todistinguish between instances for which the Price of Anarchy (PoA) can decreaseto 1 and instances for which the PoA is as large as \Omega(n^{0.121}) andcannot improve by edge removal. Thus, the network design problem for such gamesis NP-hard to approximate within a factor of O(n^{0.121-\eps}), for anyconstant \eps > 0. On the positive side, we show how to compute an almostoptimal subnetwork w.r.t. the bottleneck cost of its worst Nash flow, when theworst Nash flow in the best subnetwork routes a non-negligible amount of flowon all used edges. The running time is determined by the total number of paths,and is quasipolynomial when the number of paths is quasipolynomial.
展开▼
